package org.example.myleet.p1206;

import java.util.Random;

public class Skiplist {

    private static final int MAX_LEVEL = 10;

    private final Node head;

    private final Random random;

    public Skiplist() {
        head = new Node(-1);
        random = new Random();
    }

    /**
     * 寻找每一层刚刚好比t小的节点，nearest为一个MAX_LEVEL长度的数组
     */
    private void findNearestSmallerForEachLevel(int t, Node[] nearest) {
        Node cur = head;
        for (int i = MAX_LEVEL - 1; i >= 0; --i) {
            //从高层往第0层找，cur是第i层仅小于t的节点，或cur是第i层链表的结尾节点
            while (null != cur.next[i] && cur.next[i].val < t) {
                cur = cur.next[i];
            }
            nearest[i] = cur;
        }
    }

    public boolean search(int target) {
        Node[] nearest = new Node[MAX_LEVEL];
        findNearestSmallerForEachLevel(target, nearest);
        //第0层节点是完整链表，如果nearest[0].next[0]的节点值不等于target，那就是找不到
        return null != nearest[0].next[0] && target == nearest[0].next[0].val;
    }

    public void add(int num) {
        Node[] nearest = new Node[MAX_LEVEL];
        findNearestSmallerForEachLevel(num, nearest);
        if (null != nearest[0].next[0] && num == nearest[0].next[0].val) {
            //找到nearest[0].next[0]的值等于num，相当于链表中出现过num，直接计入count中
            ++nearest[0].next[0].count;
            return;
        }
        //链表中未出现过num，新建节点
        Node newNode = new Node(num);
        for (int i = 0; i < MAX_LEVEL; ++i) {
            //从第0层开始，新节点有50%概率被提到更高一层中
            newNode.next[i] = nearest[i].next[i];
            nearest[i].next[i] = newNode;
            if (random.nextInt(2) == 0) {
                break;
            }
        }
    }

    public boolean erase(int num) {
        Node[] nearest = new Node[MAX_LEVEL];
        findNearestSmallerForEachLevel(num, nearest);
        Node node = nearest[0].next[0];
        if (null == node || num != node.val) {
            //找不到值等于num的节点，结束删除
            return false;
        }
        //找到num值节点，count减1
        --node.count;
        if (0 == node.count) {
            //如果count减完了，则需要移除此节点，从第0层开始往更高层删除此节点
            for (int i = 0; i < MAX_LEVEL; ++i) {
                if (node != nearest[i].next[i]) {
                    //注意，当node != nearest[i].next[i]时，说明num值节点已经完全移除，无需再继续删除
                    break;
                }
                nearest[i].next[i] = nearest[i].next[i].next[i];
            }
        }
        return true;
    }

    static class Node {
        int val;
        int count;
        Node[] next;

        public Node(int val) {
            this.val = val;
            count = 1;
            next = new Node[MAX_LEVEL];
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Node{");
            sb.append("val=").append(val);
            sb.append(", count=").append(count);
            sb.append('}');
            return sb.toString();
        }
    }
}
